#include "stdio.h"
# include <stdlib.h>

#define MaxVertexNum 100    // 图中顶点数目的最大值
typedef  char VertexType;

/**
 *  ArcNode:边表节点
 */
typedef struct ArcNode{
    int adjvex;             // 该弧所指向的顶点的位置
    struct ArcNode *next;   // 指向下一条弧的指针
    int info;               // 网的边权值
} ArcNode;

/**
 *  VNode:顶点表节点
 */
typedef struct VNode{
    VertexType data;               // 顶点信息
    ArcNode *first;         // 指向第一条依附该顶点的弧指针
} VNode,AdjList[MaxVertexNum];

/**
 * ALGraph：是以邻接表存储的图类型
 */
typedef struct {
    AdjList  vertices;      // 邻接表
    int vexnum,arcnum;      // 图的顶点数和弧数
}ALGraph;                   // ALGraph 是以邻接表存储的图类型

void InitAdjGraph(ALGraph *G);

/**
 * 取x邻接顶点y的下一个邻接顶点
 * @param G
 * @param x
 * @param y
 * @return
 */
int NextNeighbor (ALGraph G,int x,int y){
    if(x!=-1) {
        ArcNode *p = G.vertices[x].first;
        while (p != NULL && p->adjvex != y){
            p = p->next;
            if(p!=NULL && p->next!=NULL)
                return p->next->adjvex;
        }
    }
}

/**
 * 初始化一个图的顶点表
 * @param G
 */
void InitAdjGraph(ALGraph *G){
    printf("请输入顶点数和边数(空格分隔)!\n");
    scanf("%d %d", &G->vexnum, &G->arcnum);
    fflush(stdout);
    printf("请输入顶点数据:\n");
    int i;
    for(i = 1; i<=G->vexnum; i++){
        printf("第%i个顶点数据为：\n",i);
        scanf("%d",&G->vertices[i].data);   // 收入每一个顶点的数据
        G->vertices[i].first = NULL;
    }
}

/**
* 接下来要进行放入有效数据，把权重放入邻接表中，由于生成无向图，所以此时要生成两个节点
*/
void CreateAdjGraph(ALGraph *G){
    printf("一共有%d条边！\n",G->arcnum);
    printf("请输入两个顶点以及两者之间的权重(中间用空格分隔):\n");
    int W,V,weight;
    int i;
    for (i = 1; i <= G->arcnum; i++) {
        scanf("%d %d %d",&W,&V,&weight);
        // 生成第一个弧节点p：加入W指向V的弧
        ArcNode *p = (ArcNode*) malloc(sizeof (ArcNode));
        // 弧p所指向的节点为V
        p->adjvex = V;
        // 弧p的权值
        p->info = weight;
        // 使用头插法将弧p加入到邻接表中
        p->next = G->vertices[W].first;
        G->vertices[W].first = p;

        // 生成第二个弧节点q:加入V指向W的弧
        ArcNode  *q = (ArcNode*) malloc(sizeof (ArcNode));
        q->adjvex = W;
        q->info = weight;
        q->next = G->vertices[V].first;
        G->vertices[V].first = q;
    }
}

void PrintAdjGraph(ALGraph *G){
    printf("将打印出邻接表的示意图！\n");
    int i;
    for (i = 1; i <= G->vexnum; i++) {
        printf("%-3d->",i);
        while (G->vertices[i].first != NULL)
        {
            printf("%-3d---weight:%-3d->",G->vertices[i].first->adjvex,G->vertices[i].first->info);
            G->vertices[i].first = G->vertices[i].first->next;
        }
        if (G->vertices[i].first == NULL)
            printf("!\n");
    }
}

